package com.lisp.algorithm.book.c15;

import java.util.Arrays;

public class LongestCommonSequence {

	public static void main(String[] args) {
		String s1 = "bsbininm";
		String s2 = "jmjkbkjkv";
	
		System.out.println(longestCommonSequence(s1, s2));
	}
	
	public static int longestCommonSequence(String text1, String text2) {
		String longer, shorter;
		if(text1.length() > text2.length()) {
			longer = text1;
			shorter = text2;
		} else {
			longer = text2;
			shorter = text1;
		}
		
		int s1Len = longer.length(), s2Len = shorter.length();
		int oldLevel[] = new int[s2Len+1];
		for(int i=1; i<s1Len+1; i++) {
			int newLevel[] = new int[s2Len+1];
			for(int j=1; j<s2Len+1; j++) {
				char l = longer.charAt(i-1);
				char s = shorter.charAt(j-1);
				if(l == s) {
					newLevel[j] = 1 + oldLevel[j-1];
				} else {
					int x = newLevel[j-1];
					int y = oldLevel[j];
					newLevel[j] = Math.max(x, y);
				}
			}
			oldLevel = newLevel;
			System.out.println(Arrays.toString(oldLevel));
		}
		return oldLevel[s2Len];
	}
}
